#!/usr/bin/env python
# coding: utf-8

# # 归并排序算法

def Union(L1, L2):
    '''
    Union two ordered list.
    '''
    i = 0
    j = 0
    L = []
    while i < len(L1) and j < len(L2):
        if L1[i] <= L2[j]:
            L.append(L1[i])
            i += 1
        elif L1[i] > L2[j]:
            L.append(L2[j])
            j += 1
        
    L = L + L1[i:] + L2[j:]
    return L

def Merge_sort(L,p,r):
    '''
    Input:
    - L: a unordered list
    - p: the start index
    - r: the end index
    Output:
    - L: a ordered list.
    '''
    if p > r:
        print('Error input.')
        return L
    if r - p == 0:
        return [L[p]]
    if r - p == 1:
        if L[r] < L[p]:
            L[r], L[p] = L[p], L[r]
        return [L[p], L[r]]
    q = int((p + r) / 2)
    left = Merge_sort(L,p,q)
    right = Merge_sort(L,q+1,r)
    return Union(left,right)





